Các thao tác Cây splay

Splay

Khi truy cập một nút x, ta thực hiện thao tác splay trên nút x để chuyển nó về vị trí gốc. Thao tác splay bao gồm nhiều bước splay, mỗi bước di chuyển x về gần gốc hơn. Việc luôn luôn thực hiện splay trên nút vừa được truy cập khiến các nút mới truy cập nằm gần gốc và cây luôn giữ hình dạng gần cân bằng.

Mỗi bước splay phụ thuộc vào ba yếu tố:

  • x là nút con trái hay phải của cha nó là p,
  • p có là nút gốc hay không, và nếu không thì
  • p là nút con trái hay phải của cha nó là g.

Sau mỗi bước splay nút cha của g là gg phải cập nhật để trỏ tới x. Nếu gg không tồn tại thì x là nút gốc mới.

Mỗi bước splay thuộc một trong ba kiểu sau:

Bước zig: Thực hiện bước này nếu p là gốc. Cây được quay trên cạnh nối x và p. Chỉ cần thực hiện phép zig khi x ở độ sâu lẻ khi thao tác splay bắt đầu.

Bước zig-zig: Thực hiện bước này khi p không là gốc và x và p đều là nút con trái hoặc đều là nút con phải. Ảnh dưới là cho trường hợp x và p đều là nút con trái (trường hợp kia hoàn toàn đối xứng). Cây quay trên cạnh nối p và cha nó là g, sau đó quay trên cạnh nối x và p. Ghi chú đây là bước duy nhất khác với phương pháp quay về gốc của Allen và Munro[2] đã được tìm ra trước cây splay.

Bước zig-zag: Thực hiện bước này khi p không là gốc và x là nút con phải và p là nút con trái hoặc ngược lại. Cây quay trên cạnh nối x và p, rồi quay trên cạnh nối x và nút cha mới là g.

Chèn

Để chèn x vào cây:

  1. Đầu tiên chèn như cây tìm kiếm nhị phân thông thường.
  2. Thực hiện thao tác splay trên x để đưa nó về gốc.

Xóa

Để xóa x, ta dùng phương pháp như cho cây nhị phân thông thường: nếu x có hai con, đổi chỗ x và nút phải nhất của cây con trái của x hoặc nút trái nhất của cây con phải của x. Sau đó xóa nút x ở vị trí mới. Bằng phương pháp này, ta luôn đưa về trường hợp xóa nút với 0 hoặc 1 nút con.

Không như cây nhị phân thông thường, sau khi xóa xong, ta thực hiện thao tác splay trên nút cha của nút mới được xóa.

HOẶC

Trước tiên thực hiện splay để đưa nút cần xóa về gốc rồi xóa. Sau đó cây bị chia cắt thành hai cây rời nhau. Thực hiện phép splay trên nút phải nhất của cây trái (cách 1), hoặc nút trái nhất của cây phải (cách 2) để đưa nó về gốc. Trong cách 1, nối cây phải vào làm cây con phải của nút gốc mới của cây trái. Nút gốc của cây trái trở thành nút gốc của cây mới hợp lại.